import java.util.ArrayList;
import java.util.List;

public class Solution906 {
    static List<Long> pal;

    static {
        pal = new ArrayList<>();
        for (int i = 1; i < 1e5; i++) {
            // odd len
            long p = i;
            for (int x = i / 10; x > 0; x /= 10) {
                p = p * 10 + x % 10;
            }
            p *= p;
            if (isPal(p)) pal.add(p);
            // even len
            p = i;
            for (int x = i; x > 0; x /= 10) {
                p = p * 10 + x % 10;
            }
            p *= p;
            if (isPal(p)) pal.add(p);
        }
        pal.sort(null);
    }

    public int superpalindromesInRange(String left, String right) {
        long L = Long.parseLong(left);
        long R = Long.parseLong(right);
        return lowerBound(pal, R) - lowerBound(pal, L - 1);
    }

    private int lowerBound(List<Long> a, long key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }

    private static boolean isPal(long x) {
        return x == reverse(x);
    }

    private static long reverse(long x) {
        long res = 0;
        while (x > 0) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}
/*
906. 超级回文数
https://leetcode.cn/problems/super-palindromes/

第 102 场周赛 T4。

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。
提示：
1 <= len(L) <= 18
1 <= len(R) <= 18
L 和 R 是表示 [1, 10^18) 范围的整数的字符串。
int(L) <= int(R)

1:1
2:4
3:9
11:121
22:484
101:10201
111:12321
121:14641
202:40804
212:44944
1001:1002001
1111:1234321
2002:4008004
10001:100020001
10101:102030201
10201:104060401
11011:121242121
11111:123454321
11211:125686521
20002:400080004
20102:404090404
100001:10000200001
101101:10221412201
110011:12102420121
111111:12345654321
200002:40000800004
1000001:1000002000001
1001001:1002003002001
1002001:1004006004001
1010101:1020304030201
1011101:1022325232201
1012101:1024348434201
1100011:1210024200121
1101011:1212225222121
1102011:1214428244121
1110111:1232346432321
1111111:1234567654321
2000002:4000008000004
2001002:4004009004004
10000001:100000020000001
10011001:100220141022001
10100101:102012040210201
10111101:102234363432201
11000011:121000242000121
11011011:121242363242121
11100111:123212464212321
11111111:123456787654321
20000002:400000080000004
100000001:10000000200000001
100010001:10002000300020001
100020001:10004000600040001
100101001:10020210401202001
100111001:10022212521222001
100121001:10024214841242001
101000101:10201020402010201
101010101:10203040504030201
101020101:10205060806050201
101101101:10221432623412201
101111101:10223454745432201
110000011:12100002420000121
110010011:12102202520220121
110020011:12104402820440121
110101011:12122232623222121
110111011:12124434743442121
111000111:12321024642012321
111010111:12323244744232321
111101111:12343456865434321
111111111:12345678987654321
200000002:40000000800000004
200010002:40004000900040004
1000000001:1000000002000000001
 */